#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
SQL语法分析器
对词法分析识别出来的单词进行语法分析，返回语法分析的结果

实现功能：
1. 定义目标语言的语法规则
2. 求解预测分析方法需要的符号集和分析表
3. 依次读入测试用例，根据预测分析的方法进行语法分析，直到源程序结束
4. 对遇到的语法错误做出错误处理
"""

from typing import Dict, List, Set, Tuple, Optional, Union
from enum import Enum
import copy
from LexicalAnalysis import LexicalAnalyzer, Token, TokenType
from ErrorCorrection import SmartErrorCorrector, ErrorInfo, ErrorType, ErrorSeverity


class SymbolType(Enum):
    """符号类型"""
    TERMINAL = 1      # 终结符
    NON_TERMINAL = 2  # 非终结符


class GrammarSymbol:
    """文法符号类"""
    
    def __init__(self, symbol: str, symbol_type: SymbolType):
        self.symbol = symbol
        self.type = symbol_type
    
    def __str__(self):
        return self.symbol
    
    def __repr__(self):
        return f"{self.symbol}({self.type.name})"
    
    def __eq__(self, other):
        if isinstance(other, GrammarSymbol):
            return self.symbol == other.symbol and self.type == other.type
        return False
    
    def __hash__(self):
        return hash((self.symbol, self.type))


class Production:
    """产生式类"""
    
    def __init__(self, left: str, right: List[str]):
        self.left = left          # 产生式左部
        self.right = right        # 产生式右部
    
    def __str__(self):
        return f"{self.left} -> {' '.join(self.right)}"
    
    def __repr__(self):
        return self.__str__()
    
    def __eq__(self, other):
        if isinstance(other, Production):
            return self.left == other.left and self.right == other.right
        return False
    
    def __hash__(self):
        return hash((self.left, tuple(self.right)))


class SyntaxAnalyzer:
    """语法分析器"""
    
    def __init__(self):
        # 特殊符号
        self.EPSILON = 'ε'        # 空字符
        self.EOF_SYMBOL = '$'     # 结束符
        self.START_SYMBOL = 'S'   # 开始符号
        
        # 文法定义
        self.terminals = set()      # 终结符集合
        self.non_terminals = set()  # 非终结符集合
        self.productions = []       # 产生式集合
        self.start_symbol = None    # 开始符号
        
        # 预测分析需要的集合
        self.first_sets = {}        # FIRST集合
        self.follow_sets = {}       # FOLLOW集合
        self.ll1_table = {}         # LL(1)预测分析表
        
        # 智能纠错器
        self.error_corrector = SmartErrorCorrector()
        self.parse_errors = []      # 存储解析错误
        
        # 初始化SQL文法
        self._init_sql_grammar()
    
    def _init_sql_grammar(self):
        """初始化SQL文法规则"""
        
        # 定义非终结符
        self.non_terminals = {
            'Prog',         # 程序
            'Stmt',         # SQL语句
            'SelectStmt',   # SELECT语句
            'SimpleSelect', # 简单SELECT语句
            'CreateStmt',   # CREATE语句
            'CreateTarget', # CREATE目标（TABLE或DATABASE）
            'InsertStmt',   # INSERT语句
            'DeleteStmt',   # DELETE语句
            'UpdateStmt',   # UPDATE语句
            'DropStmt',     # DROP语句
            'DropTarget',   # DROP目标（TABLE或DATABASE）
            'UseStmt',      # USE语句
            'GrantStmt',    # GRANT语句
            'ListStmt',     # LIST/SHOW语句
            'ListTarget',   # LIST/SHOW目标（DATABASES或SCHEMAS）
            'UserSpec',     # 用户规格（密码相关）
            'SelList',      # 选择列表
            'SelRest',      # 选择列表剩余部分
            'ColDef',       # 列定义
            'ColDefList',   # 列定义列表
            'ColDefRest',   # 列定义剩余部分
            'DataType',     # 数据类型
            'VarcharSize',  # VARCHAR长度规格
            'ValueList',    # 值列表
            'ValueRest',    # 值列表剩余部分
            'WhereClause',  # WHERE子句
            'Condition',    # 条件表达式
            'LogicalExpr',  # 逻辑表达式
            'LogicalRest',  # 逻辑表达式剩余部分
            'LogicalOp',    # 逻辑操作符
            'SimpleCondition', # 简单条件
            'CompOp',       # 比较操作符
            'Tbl',          # 表名
            'ID',           # 标识符
            'QualifiedID',  # 限定标识符 (table.column)
            'FromClause',   # FROM子句
            'JoinClause',   # JOIN子句
            'JoinType',     # JOIN类型
            'OrderClause',  # ORDER BY子句
            'GroupClause',  # GROUP BY子句
            'SetList',      # SET列表
            'SetItem',      # SET项
            'SetRest',      # SET剩余部分
            'OrderList',    # ORDER列表
            'OrderItem',    # ORDER项
            'OrderExpression', # ORDER表达式
            'OrderRest',    # ORDER剩余部分
            'GroupList',    # GROUP列表
            'GroupRest',    # GROUP剩余部分
            'TblAlias',     # 表别名
            'TableIdentifier', # 表标识符（可以是ID或某些关键字）
            'Value',        # 值
            'QualifiedIDRest', # 限定标识符剩余部分
            'TblAliasRest', # 表别名剩余部分
            'OrderDir',     # 排序方向
            'CondValue',    # 条件值
            'LimitClause',  # LIMIT子句
            'UnionClause',  # UNION子句
            'UnionRest',    # UNION剩余部分
            'UnionType',    # UNION类型
            'AggregateFunc', # 聚合函数
            'AggregateType', # 聚合函数类型
            'AggregateParam', # 聚合函数参数
            'SelectItem',    # 选择项（支持聚合函数）
            'HavingClause',  # HAVING子句
            'PrivilegeList', # 权限列表
            'PrivilegeItem', # 权限项
            'PrivilegeRest', # 权限列表剩余部分
            'AllPrivileges', # ALL权限处理
            'GranteeList',   # 被授权者列表
            'GranteeRest',   # 被授权者列表剩余部分
            'ObjectType',    # 对象类型
            'GrantOption'    # GRANT选项
        }
        
        # 定义终结符（基于词法分析器的Token类型）
        self.terminals = {
            'SELECT', 'FROM', 'WHERE', 'CREATE', 'TABLE', 'INSERT', 'INTO',
            'UPDATE', 'DELETE', 'VALUES', 'INT', 'VARCHAR', 'ID_TOKEN',
            'JOIN', 'INNER', 'LEFT', 'RIGHT', 'FULL', 'OUTER', 'ON',
            'ORDER', 'BY', 'GROUP', 'SET', 'ASC', 'DESC', 'USE', 'AND', 'OR', 'LIKE',
            'LIMIT', 'UNION', 'ALL', 'HAVING', 'GRANT', 'REVOKE', 'TO', 'WITH',
            'OPTION', 'PRIVILEGES', 'PUBLIC', 'ROLE', 'USER', 'DATABASE', 'DROP', 'ALTER',
            # 数据库管理相关终结符
            'LIST', 'SHOW', 'DATABASES', 'SCHEMAS',
            # 用户管理相关终结符
            'USERS', 'PASSWORD', 'IDENTIFIED',
            # 聚合函数关键字
            'COUNT', 'SUM', 'AVG', 'MAX', 'MIN', 'STDDEV', 'VARIANCE',
            ',', ';', '.', '(', ')', '>', '<', '=', '!=', '>=', '<=', '*',
            'NUM', 'STRING', self.EOF_SYMBOL, self.EPSILON
        }
        
        # 设置开始符号
        self.start_symbol = 'Prog'
        
        # 定义产生式（消除左递归并修正LL(1)冲突）
        self.productions = [
            # Prog -> Stmt ;
            Production('Prog', ['Stmt', ';']),
            
            # Stmt -> SelectStmt | CreateStmt | InsertStmt | DeleteStmt | UpdateStmt | DropStmt | UseStmt | GrantStmt | ListStmt
            Production('Stmt', ['SelectStmt']),
            Production('Stmt', ['CreateStmt']),
            Production('Stmt', ['InsertStmt']),
            Production('Stmt', ['DeleteStmt']),
            Production('Stmt', ['UpdateStmt']),
            Production('Stmt', ['DropStmt']),
            Production('Stmt', ['UseStmt']),
            Production('Stmt', ['GrantStmt']),
            Production('Stmt', ['ListStmt']),
            
            # SelectStmt -> SimpleSelect UnionClause
            Production('SelectStmt', ['SimpleSelect', 'UnionClause']),
            
            # SimpleSelect -> SELECT SelList FromClause WhereClause GroupClause HavingClause OrderClause LimitClause (标准SQL顺序)
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'HavingClause', 'OrderClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'HavingClause', 'OrderClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'HavingClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'HavingClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'OrderClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'OrderClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'GroupClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'OrderClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'OrderClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'WhereClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'HavingClause', 'OrderClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'HavingClause', 'OrderClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'HavingClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'HavingClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'OrderClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'OrderClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'GroupClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'OrderClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'OrderClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause', 'LimitClause']),
            Production('SimpleSelect', ['SELECT', 'SelList', 'FromClause']),
            
            # CreateStmt -> CREATE CreateTarget
            Production('CreateStmt', ['CREATE', 'CreateTarget']),
            
            # CreateTarget -> TABLE ID ( ColDefList ) | DATABASE ID | USER ID UserSpec
            Production('CreateTarget', ['TABLE', 'ID', '(', 'ColDefList', ')']),
            Production('CreateTarget', ['DATABASE', 'ID']),
            Production('CreateTarget', ['USER', 'ID', 'UserSpec']),
            
            # InsertStmt -> INSERT INTO ID ( SelList ) VALUES ( ValueList ) | INSERT INTO ID VALUES ( ValueList )
            Production('InsertStmt', ['INSERT', 'INTO', 'ID', '(', 'SelList', ')', 'VALUES', '(', 'ValueList', ')']),
            Production('InsertStmt', ['INSERT', 'INTO', 'ID', 'VALUES', '(', 'ValueList', ')']),
            
            # DeleteStmt -> DELETE FROM ID WhereClause
            Production('DeleteStmt', ['DELETE', 'FROM', 'ID', 'WhereClause']),
            
            # UpdateStmt -> UPDATE ID SET SetList WhereClause
            Production('UpdateStmt', ['UPDATE', 'ID', 'SET', 'SetList', 'WhereClause']),
            Production('UpdateStmt', ['UPDATE', 'ID', 'SET', 'SetList']),
            
            # DropStmt -> DROP DropTarget
            Production('DropStmt', ['DROP', 'DropTarget']),
            
            # DropTarget -> TABLE ID | DATABASE ID | USER ID
            Production('DropTarget', ['TABLE', 'ID']),
            Production('DropTarget', ['DATABASE', 'ID']),
            Production('DropTarget', ['USER', 'ID']),
            
            # UseStmt -> USE ID
            Production('UseStmt', ['USE', 'ID']),
            
            # ListStmt -> LIST ListTarget | SHOW ListTarget
            Production('ListStmt', ['LIST', 'ListTarget']),
            Production('ListStmt', ['SHOW', 'ListTarget']),
            
            # ListTarget -> DATABASES | SCHEMAS | USERS
            Production('ListTarget', ['DATABASES']),
            Production('ListTarget', ['SCHEMAS']),
            Production('ListTarget', ['USERS']),
            
            
            # SelList -> SelectItem SelRest | *
            Production('SelList', ['SelectItem', 'SelRest']),
            Production('SelList', ['*']),
            
            # SelectItem -> QualifiedID | AggregateFunc
            Production('SelectItem', ['QualifiedID']),
            Production('SelectItem', ['AggregateFunc']),
            
            # SelRest -> , SelList | ε
            Production('SelRest', [',', 'SelList']),
            Production('SelRest', [self.EPSILON]),
            
            # ColDefList -> ColDef ColDefRest
            Production('ColDefList', ['ColDef', 'ColDefRest']),
            
            # ColDefRest -> , ColDefList | ε
            Production('ColDefRest', [',', 'ColDefList']),
            Production('ColDefRest', [self.EPSILON]),
            
            # ColDef -> ID DataType
            Production('ColDef', ['ID', 'DataType']),
            
            # DataType -> INT | VARCHAR VarcharSize
            Production('DataType', ['INT']),
            Production('DataType', ['VARCHAR', 'VarcharSize']),
            
            # VarcharSize -> ( NUM ) | ε
            Production('VarcharSize', ['(', 'NUM', ')']),
            Production('VarcharSize', [self.EPSILON]),
            
            # ValueList -> STRING ValueRest | NUM ValueRest
            Production('ValueList', ['STRING', 'ValueRest']),
            Production('ValueList', ['NUM', 'ValueRest']),
            
            # ValueRest -> , ValueList | ε
            Production('ValueRest', [',', 'ValueList']),
            Production('ValueRest', [self.EPSILON]),
            
            # WhereClause -> WHERE Condition | ε
            Production('WhereClause', ['WHERE', 'Condition']),
            Production('WhereClause', [self.EPSILON]),
            
            # Condition -> LogicalExpr
            Production('Condition', ['LogicalExpr']),
            
            # LogicalExpr -> SimpleCondition LogicalRest
            Production('LogicalExpr', ['SimpleCondition', 'LogicalRest']),
            
            # LogicalRest -> LogicalOp LogicalExpr | ε
            Production('LogicalRest', ['LogicalOp', 'LogicalExpr']),
            Production('LogicalRest', [self.EPSILON]),
            
            # LogicalOp -> AND | OR
            Production('LogicalOp', ['AND']),
            Production('LogicalOp', ['OR']),
            
            # SimpleCondition -> QualifiedID CompOp CondValue | AggregateFunc CompOp CondValue | ( Condition )
            Production('SimpleCondition', ['QualifiedID', 'CompOp', 'CondValue']),
            Production('SimpleCondition', ['AggregateFunc', 'CompOp', 'CondValue']),
            Production('SimpleCondition', ['(', 'Condition', ')']),
            
            # CondValue -> NUM | STRING | QualifiedID | ( SelectStmt )
            Production('CondValue', ['NUM']),
            Production('CondValue', ['STRING']),
            Production('CondValue', ['QualifiedID']),
            Production('CondValue', ['(', 'SelectStmt', ')']),
            
            # CompOp -> = | > | < | >= | <= | != | LIKE
            Production('CompOp', ['=']),
            Production('CompOp', ['>']),
            Production('CompOp', ['<']),
            Production('CompOp', ['>=']),
            Production('CompOp', ['<=']),
            Production('CompOp', ['!=']),
            Production('CompOp', ['LIKE']),
            
            # Tbl -> ID
            Production('Tbl', ['ID']),
            
            # ID -> ID_TOKEN
            Production('ID', ['ID_TOKEN']),
            
            # FromClause -> FROM TblAlias JoinClause | FROM TblAlias
            Production('FromClause', ['FROM', 'TblAlias', 'JoinClause']),
            Production('FromClause', ['FROM', 'TblAlias']),
            
            # JoinClause -> JoinType JOIN TblAlias ON Condition JoinClause | JoinType JOIN TblAlias ON Condition | ε
            Production('JoinClause', ['JoinType', 'JOIN', 'TblAlias', 'ON', 'Condition', 'JoinClause']),
            Production('JoinClause', ['JoinType', 'JOIN', 'TblAlias', 'ON', 'Condition']),
            Production('JoinClause', [self.EPSILON]),
            
            # JoinType -> INNER | LEFT | RIGHT | FULL OUTER | ε
            Production('JoinType', ['INNER']),
            Production('JoinType', ['LEFT']),
            Production('JoinType', ['RIGHT']),
            Production('JoinType', ['FULL', 'OUTER']),
            Production('JoinType', [self.EPSILON]),
            
            # OrderClause -> ORDER BY OrderList | ε
            Production('OrderClause', ['ORDER', 'BY', 'OrderList']),
            Production('OrderClause', [self.EPSILON]),
            
            # OrderList -> OrderItem OrderRest
            Production('OrderList', ['OrderItem', 'OrderRest']),
            
            # OrderRest -> , OrderList | ε
            Production('OrderRest', [',', 'OrderList']),
            Production('OrderRest', [self.EPSILON]),
            
            # OrderItem -> OrderExpression OrderDir
            Production('OrderItem', ['OrderExpression', 'OrderDir']),
            
            # OrderExpression -> QualifiedID | AggregateFunc
            Production('OrderExpression', ['QualifiedID']),
            Production('OrderExpression', ['AggregateFunc']),
            
            # OrderDir -> ASC | DESC | ε
            Production('OrderDir', ['ASC']),
            Production('OrderDir', ['DESC']),
            Production('OrderDir', [self.EPSILON]),
            
            # GroupClause -> GROUP BY GroupList | ε
            Production('GroupClause', ['GROUP', 'BY', 'GroupList']),
            Production('GroupClause', [self.EPSILON]),
            
            # HavingClause -> HAVING Condition | ε
            Production('HavingClause', ['HAVING', 'Condition']),
            Production('HavingClause', [self.EPSILON]),
            
            # GroupList -> QualifiedID GroupRest
            Production('GroupList', ['QualifiedID', 'GroupRest']),
            
            # GroupRest -> , GroupList | ε
            Production('GroupRest', [',', 'GroupList']),
            Production('GroupRest', [self.EPSILON]),
            
            # SetList -> SetItem SetRest
            Production('SetList', ['SetItem', 'SetRest']),
            
            # SetRest -> , SetList | ε
            Production('SetRest', [',', 'SetList']),
            Production('SetRest', [self.EPSILON]),
            
            # SetItem -> ID = Value
            Production('SetItem', ['ID', '=', 'Value']),
            
            # Value -> STRING | NUM
            Production('Value', ['STRING']),
            Production('Value', ['NUM']),
            
            # QualifiedID -> ID QualifiedIDRest
            Production('QualifiedID', ['ID', 'QualifiedIDRest']),
            
            # QualifiedIDRest -> . ID | ε
            Production('QualifiedIDRest', ['.', 'ID']),
            Production('QualifiedIDRest', [self.EPSILON]),
            
            # TblAlias -> TableIdentifier TblAliasRest
            Production('TblAlias', ['TableIdentifier', 'TblAliasRest']),
            
            # TableIdentifier -> ID | USERS | DATABASES | SCHEMAS
            Production('TableIdentifier', ['ID']),
            Production('TableIdentifier', ['USERS']),
            Production('TableIdentifier', ['DATABASES']),
            Production('TableIdentifier', ['SCHEMAS']),
            
            # TblAliasRest -> ID | ε
            Production('TblAliasRest', ['ID']),
            Production('TblAliasRest', [self.EPSILON]),
            
            # LimitClause -> LIMIT NUM | ε
            Production('LimitClause', ['LIMIT', 'NUM']),
            Production('LimitClause', [self.EPSILON]),
            
            # UnionClause -> UNION UnionType SimpleSelect UnionRest | ε
            Production('UnionClause', ['UNION', 'UnionType', 'SimpleSelect', 'UnionRest']),
            Production('UnionClause', [self.EPSILON]),
            
            # UnionType -> ALL | ε
            Production('UnionType', ['ALL']),
            Production('UnionType', [self.EPSILON]),
            
            # UnionRest -> UnionClause | ε
            Production('UnionRest', ['UnionClause']),
            Production('UnionRest', [self.EPSILON]),
            
            # AggregateFunc -> AggregateType ( AggregateParam )
            Production('AggregateFunc', ['AggregateType', '(', 'AggregateParam', ')']),
            
            # AggregateParam -> * | QualifiedID
            Production('AggregateParam', ['*']),
            Production('AggregateParam', ['QualifiedID']),
            
            # AggregateType -> COUNT | SUM | AVG | MAX | MIN | STDDEV | VARIANCE
            Production('AggregateType', ['COUNT']),
            Production('AggregateType', ['SUM']),
            Production('AggregateType', ['AVG']),
            Production('AggregateType', ['MAX']),
            Production('AggregateType', ['MIN']),
            Production('AggregateType', ['STDDEV']),
            Production('AggregateType', ['VARIANCE']),
            
            # GrantStmt -> GRANT PrivilegeList ON ObjectType ID TO GranteeList GrantOption
            Production('GrantStmt', ['GRANT', 'PrivilegeList', 'ON', 'ObjectType', 'ID', 'TO', 'GranteeList', 'GrantOption']),
            Production('GrantStmt', ['GRANT', 'PrivilegeList', 'ON', 'ObjectType', 'ID', 'TO', 'GranteeList']),
            Production('GrantStmt', ['GRANT', 'PrivilegeList', 'ON', 'ID', 'TO', 'GranteeList', 'GrantOption']),
            Production('GrantStmt', ['GRANT', 'PrivilegeList', 'ON', 'ID', 'TO', 'GranteeList']),
            
            # PrivilegeList -> PrivilegeItem PrivilegeRest | ALL AllPrivileges
            Production('PrivilegeList', ['PrivilegeItem', 'PrivilegeRest']),
            Production('PrivilegeList', ['ALL', 'AllPrivileges']),
            
            # AllPrivileges -> PRIVILEGES | ε
            Production('AllPrivileges', ['PRIVILEGES']),
            Production('AllPrivileges', [self.EPSILON]),
            
            # PrivilegeRest -> , PrivilegeList | ε
            Production('PrivilegeRest', [',', 'PrivilegeList']),
            Production('PrivilegeRest', [self.EPSILON]),
            
            # PrivilegeItem -> SELECT | INSERT | UPDATE | DELETE | CREATE | DROP | ALTER
            Production('PrivilegeItem', ['SELECT']),
            Production('PrivilegeItem', ['INSERT']),
            Production('PrivilegeItem', ['UPDATE']),
            Production('PrivilegeItem', ['DELETE']),
            Production('PrivilegeItem', ['CREATE']),
            Production('PrivilegeItem', ['DROP']),
            Production('PrivilegeItem', ['ALTER']),
            
            # ObjectType -> TABLE | DATABASE | ε
            Production('ObjectType', ['TABLE']),
            Production('ObjectType', ['DATABASE']),
            Production('ObjectType', [self.EPSILON]),
            
            # GranteeList -> ID GranteeRest | PUBLIC | ROLE ID | USER ID
            Production('GranteeList', ['ID', 'GranteeRest']),
            Production('GranteeList', ['PUBLIC']),
            Production('GranteeList', ['ROLE', 'ID']),
            Production('GranteeList', ['USER', 'ID']),
            
            # GranteeRest -> , GranteeList | ε
            Production('GranteeRest', [',', 'GranteeList']),
            Production('GranteeRest', [self.EPSILON]),
            
            # GrantOption -> WITH GRANT OPTION | ε
            Production('GrantOption', ['WITH', 'GRANT', 'OPTION']),
            Production('GrantOption', [self.EPSILON]),
            
            
            # UserSpec -> IDENTIFIED BY STRING | ε
            Production('UserSpec', ['IDENTIFIED', 'BY', 'STRING']),
            Production('UserSpec', [self.EPSILON]),
        ]
        
        print("初始文法:")
        for i, prod in enumerate(self.productions):
            print(f"({i+1}) {prod}")
    
    def eliminate_left_recursion(self):
        """消除直接左递归"""
        print("\n=== 消除左递归 ===")
        
        # 按照算法，对每个非终结符按顺序处理
        non_terminals_list = list(self.non_terminals)
        new_productions = []
        
        for A in non_terminals_list:
            # 找到所有以A为左部的产生式
            A_productions = [p for p in self.productions if p.left == A]
            
            # 分离直接左递归和非左递归产生式
            left_recursive = []
            non_left_recursive = []
            
            for prod in A_productions:
                if len(prod.right) > 0 and prod.right[0] == A:
                    # 直接左递归：A -> Aα
                    left_recursive.append(prod.right[1:])  # α部分
                else:
                    # 非左递归：A -> β
                    non_left_recursive.append(prod.right)
            
            if left_recursive:
                # 存在左递归，需要消除
                print(f"发现 {A} 的左递归，正在消除...")
                
                # 创建新的非终结符 A'
                A_prime = A + "'"
                self.non_terminals.add(A_prime)
                
                # 对于每个非左递归产生式 A -> β，改写为 A -> βA'
                for beta in non_left_recursive:
                    new_productions.append(Production(A, beta + [A_prime]))
                
                # 对于每个左递归产生式 A -> Aα，改写为 A' -> αA'
                for alpha in left_recursive:
                    new_productions.append(Production(A_prime, alpha + [A_prime]))
                
                # 添加 A' -> ε
                new_productions.append(Production(A_prime, [self.EPSILON]))
                
                print(f"  消除后的产生式:")
                for prod in new_productions[-len(non_left_recursive)-len(left_recursive)-1:]:
                    print(f"    {prod}")
            else:
                # 没有左递归，保持原产生式
                for beta in non_left_recursive:
                    new_productions.append(Production(A, beta))
        
        # 添加其他非终结符的产生式
        for prod in self.productions:
            if prod.left not in non_terminals_list:
                new_productions.append(prod)
        
        self.productions = new_productions
        
        print("\n消除左递归后的文法:")
        for i, prod in enumerate(self.productions):
            print(f"({i+1}) {prod}")
    
    def compute_first_sets(self):
        """计算FIRST集合"""
        print("\n=== 计算FIRST集合 ===")
        
        # 初始化FIRST集合
        for symbol in self.terminals | self.non_terminals:
            self.first_sets[symbol] = set()
        
        # 对于终结符，FIRST集合就是它本身
        for terminal in self.terminals:
            self.first_sets[terminal] = {terminal}
        
        # 迭代计算非终结符的FIRST集合
        changed = True
        while changed:
            changed = False
            
            for production in self.productions:
                A = production.left
                right = production.right
                
                # 如果产生式是 A -> ε
                if len(right) == 1 and right[0] == self.EPSILON:
                    if self.EPSILON not in self.first_sets[A]:
                        self.first_sets[A].add(self.EPSILON)
                        changed = True
                    continue
                
                # 计算 FIRST(α1α2...αk)
                first_of_right = set()
                all_have_epsilon = True
                
                for symbol in right:
                    symbol_first = self.first_sets[symbol].copy()
                    first_of_right |= (symbol_first - {self.EPSILON})
                    
                    if self.EPSILON not in symbol_first:
                        all_have_epsilon = False
                        break
                
                if all_have_epsilon:
                    first_of_right.add(self.EPSILON)
                
                # 将计算结果加入FIRST(A)
                old_size = len(self.first_sets[A])
                self.first_sets[A] |= first_of_right
                if len(self.first_sets[A]) > old_size:
                    changed = True
        
        # 打印FIRST集合
        print("FIRST集合:")
        for symbol in sorted(self.non_terminals | self.terminals):
            if symbol in self.first_sets and self.first_sets[symbol]:
                print(f"  FIRST({symbol}) = {{{', '.join(sorted(self.first_sets[symbol]))}}}")
    
    def compute_follow_sets(self):
        """计算FOLLOW集合"""
        print("\n=== 计算FOLLOW集合 ===")
        
        # 初始化FOLLOW集合
        for symbol in self.non_terminals:
            self.follow_sets[symbol] = set()
        
        # 将$加入FOLLOW(S)，S是开始符号
        self.follow_sets[self.start_symbol].add(self.EOF_SYMBOL)
        
        # 迭代计算FOLLOW集合
        changed = True
        while changed:
            changed = False
            
            for production in self.productions:
                right = production.right
                
                for i, symbol in enumerate(right):
                    if symbol in self.non_terminals:
                        # 计算β = α_{i+1}...α_n
                        beta = right[i+1:]
                        
                        if not beta:
                            # β为空，将FOLLOW(A)加入FOLLOW(symbol)
                            old_size = len(self.follow_sets[symbol])
                            self.follow_sets[symbol] |= self.follow_sets[production.left]
                            if len(self.follow_sets[symbol]) > old_size:
                                changed = True
                        else:
                            # 计算FIRST(β)
                            first_beta = set()
                            all_have_epsilon = True
                            
                            for beta_symbol in beta:
                                beta_first = self.first_sets[beta_symbol].copy()
                                first_beta |= (beta_first - {self.EPSILON})
                                
                                if self.EPSILON not in beta_first:
                                    all_have_epsilon = False
                                    break
                            
                            # 将FIRST(β) - {ε}加入FOLLOW(symbol)
                            old_size = len(self.follow_sets[symbol])
                            self.follow_sets[symbol] |= first_beta
                            if len(self.follow_sets[symbol]) > old_size:
                                changed = True
                            
                            # 如果ε ∈ FIRST(β)，将FOLLOW(A)加入FOLLOW(symbol)
                            if all_have_epsilon:
                                old_size = len(self.follow_sets[symbol])
                                self.follow_sets[symbol] |= self.follow_sets[production.left]
                                if len(self.follow_sets[symbol]) > old_size:
                                    changed = True
        
        # 打印FOLLOW集合
        print("FOLLOW集合:")
        for symbol in sorted(self.non_terminals):
            if symbol in self.follow_sets and self.follow_sets[symbol]:
                print(f"  FOLLOW({symbol}) = {{{', '.join(sorted(self.follow_sets[symbol]))}}}")
    
    def construct_ll1_table(self):
        """构造LL(1)预测分析表"""
        print("\n=== 构造LL(1)预测分析表 ===")
        
        # 初始化分析表
        self.ll1_table = {}
        for non_terminal in self.non_terminals:
            self.ll1_table[non_terminal] = {}
        
        # 对每个产生式A -> α
        for production in self.productions:
            A = production.left
            alpha = production.right
            
            # 计算FIRST(α)
            first_alpha = set()
            all_have_epsilon = True
            
            if len(alpha) == 1 and alpha[0] == self.EPSILON:
                first_alpha.add(self.EPSILON)
            else:
                for symbol in alpha:
                    symbol_first = self.first_sets[symbol].copy()
                    first_alpha |= (symbol_first - {self.EPSILON})
                    
                    if self.EPSILON not in symbol_first:
                        all_have_epsilon = False
                        break
                
                if all_have_epsilon:
                    first_alpha.add(self.EPSILON)
            
            # 对于FIRST(α)中的每个终结符a，将A -> α加入M[A,a]
            for terminal in first_alpha - {self.EPSILON}:
                if terminal in self.ll1_table[A]:
                    print(f"警告: 文法不是LL(1)的，M[{A},{terminal}]有冲突")
                else:
                    self.ll1_table[A][terminal] = production
            
            # 如果ε ∈ FIRST(α)，对于FOLLOW(A)中的每个符号b，将A -> α加入M[A,b]
            if self.EPSILON in first_alpha:
                for follow_symbol in self.follow_sets[A]:
                    if follow_symbol in self.ll1_table[A]:
                        print(f"警告: 文法不是LL(1)的，M[{A},{follow_symbol}]有冲突")
                    else:
                        self.ll1_table[A][follow_symbol] = production
        
        # 打印LL(1)分析表
        print("LL(1)预测分析表:")
        print(f"{'非终结符':<10}", end='')
        all_terminals = sorted(self.terminals - {self.EPSILON})
        for terminal in all_terminals:
            print(f"{terminal:<12}", end='')
        print()
        
        for non_terminal in sorted(self.non_terminals):
            print(f"{non_terminal:<10}", end='')
            for terminal in all_terminals:
                if terminal in self.ll1_table[non_terminal]:
                    prod = self.ll1_table[non_terminal][terminal]
                    print(f"{' '.join(prod.right):<12}", end='')
                else:
                    print(f"{'error':<12}", end='')
            print()
    
    def predictive_parse(self, tokens: List[Token]) -> bool:
        """预测分析算法"""
        print("\n=== 预测分析过程 ===")
        
        # 清空错误记录
        self.error_corrector.clear_errors()
        self.parse_errors.clear()
        
        # 初始化栈和输入
        stack = [self.EOF_SYMBOL, self.start_symbol]  # 栈底到栈顶
        input_buffer = []
        token_positions = []  # 保存每个输入符号对应的Token位置信息
        
        # 将tokens转换为终结符序列，同时保存位置信息
        for token in tokens:
            if token.type == TokenType.KEYWORD:
                # 特殊处理聚合函数关键字
                keyword_upper = token.value.upper()
                if keyword_upper in {'COUNT', 'SUM', 'AVG', 'MAX', 'MIN', 'STDDEV', 'VARIANCE'}:
                    input_buffer.append(keyword_upper)
                else:
                    input_buffer.append(keyword_upper)
                token_positions.append(token)
            elif token.type == TokenType.IDENTIFIER:
                input_buffer.append('ID_TOKEN')
                token_positions.append(token)
            elif token.type == TokenType.CONSTANT:
                input_buffer.append('NUM' if token.value.isdigit() else 'STRING')
                token_positions.append(token)
            elif token.type == TokenType.DELIMITER:
                input_buffer.append(token.value)
                token_positions.append(token)
            elif token.type == TokenType.OPERATOR:
                input_buffer.append(token.value)
                token_positions.append(token)
            elif token.type == TokenType.EOF:
                input_buffer.append(self.EOF_SYMBOL)
                token_positions.append(token)
        
        # 确保输入以$结尾
        if not input_buffer or input_buffer[-1] != self.EOF_SYMBOL:
            input_buffer.append(self.EOF_SYMBOL)
            # 为EOF符号创建一个位置信息
            if token_positions:
                last_token = token_positions[-1]
                eof_token = Token(TokenType.EOF, "EOF", last_token.line, last_token.column + len(last_token.value))
            else:
                eof_token = Token(TokenType.EOF, "EOF", 1, 1)
            token_positions.append(eof_token)
        
        input_index = 0
        step = 0
        
        print(f"输入串: {' '.join(input_buffer)}")
        print(f"{'步骤':<4} {'栈':<20} {'输入':<15} {'动作':<30}")
        print("-" * 70)
        
        while len(stack) > 1:  # 栈中还有符号（除了$）
            step += 1
            current_stack = ' '.join(reversed(stack))
            remaining_input = ' '.join(input_buffer[input_index:])
            
            top = stack[-1]  # 栈顶符号
            current_input = input_buffer[input_index] if input_index < len(input_buffer) else self.EOF_SYMBOL
            
            if top in self.terminals:
                # 栈顶是终结符
                if top == current_input:
                    # 匹配成功
                    stack.pop()
                    input_index += 1
                    action = f"匹配 {top}"
                    print(f"{step:<4} {current_stack:<20} {remaining_input:<15} {action:<30}")
                else:
                    # 匹配失败 - 输出详细错误信息并尝试智能纠错
                    if input_index < len(token_positions):
                        error_token = token_positions[input_index]
                        error_msg = (f"语法错误: 在第{error_token.line}行第{error_token.column}列处，"
                                   f"期望符号 '{top}'，但得到了 '{current_input}' (值: '{error_token.value}')")
                        print(f"\n{error_msg}")
                        print(f"错误位置上下文: ...{self._get_context(tokens, input_index)}...")
                        
                        # 记录错误并尝试修复
                        self._record_syntax_error(error_token, f"期望 '{top}'，得到 '{current_input}'", top, current_input)
                    else:
                        print(f"\n语法错误: 期望符号 '{top}'，但输入已结束")
                        self._record_syntax_error(None, f"期望 '{top}'，但输入已结束", top, "EOF")
                    
                    action = f"错误: 期望 {top}，得到 {current_input}"
                    print(f"{step:<4} {current_stack:<20} {remaining_input:<15} {action:<30}")
                    return False
            
            elif top in self.non_terminals:
                # 栈顶是非终结符
                if top in self.ll1_table and current_input in self.ll1_table[top]:
                    # 查表成功
                    production = self.ll1_table[top][current_input]
                    stack.pop()  # 弹出非终结符
                    
                    # 将产生式右部压入栈（逆序）
                    if not (len(production.right) == 1 and production.right[0] == self.EPSILON):
                        for symbol in reversed(production.right):
                            stack.append(symbol)
                    
                    action = f"用 {production} 推导"
                    print(f"{step:<4} {current_stack:<20} {remaining_input:<15} {action:<30}")
                else:
                    # 查表失败 - 输出详细错误信息并尝试智能纠错
                    if input_index < len(token_positions):
                        error_token = token_positions[input_index]
                        expected_symbols = self._get_expected_symbols(top)
                        error_msg = (f"语法错误: 在第{error_token.line}行第{error_token.column}列处，"
                                   f"遇到意外的符号 '{current_input}' (值: '{error_token.value}')")
                        print(f"\n{error_msg}")
                        if expected_symbols:
                            print(f"期望的符号: {', '.join(expected_symbols)}")
                        print(f"当前处理的非终结符: {top}")
                        print(f"错误位置上下文: ...{self._get_context(tokens, input_index)}...")
                        
                        # 记录错误并尝试修复
                        self._record_parse_table_error(error_token, top, current_input, expected_symbols)
                    else:
                        expected_symbols = self._get_expected_symbols(top)
                        print(f"\n语法错误: 输入意外结束")
                        if expected_symbols:
                            print(f"期望的符号: {', '.join(expected_symbols)}")
                        print(f"当前处理的非终结符: {top}")
                        
                        # 记录错误
                        self._record_parse_table_error(None, top, "EOF", expected_symbols)
                    
                    action = f"错误: M[{top},{current_input}] 为空"
                    print(f"{step:<4} {current_stack:<20} {remaining_input:<15} {action:<30}")
                    return False
            else:
                # 未知符号
                if input_index < len(token_positions):
                    error_token = token_positions[input_index]
                    print(f"\n内部错误: 在第{error_token.line}行第{error_token.column}列处，遇到未知符号 '{top}'")
                else:
                    print(f"\n内部错误: 遇到未知符号 '{top}'")
                
                action = f"错误: 未知符号 {top}"
                print(f"{step:<4} {current_stack:<20} {remaining_input:<15} {action:<30}")
                return False
        
        # 检查是否成功接受
        if input_index >= len(input_buffer) or input_buffer[input_index] == self.EOF_SYMBOL:
            print("分析成功！程序被接受。")
            return True
        else:
            print("分析失败！输入未完全消耗。")
            return False
    
    def analyze(self, tokens: List[Token]) -> bool:
        """完整的语法分析过程"""
        print("=== 开始语法分析 ===")
        
        # 1. 消除左递归
        self.eliminate_left_recursion()
        
        # 2. 计算FIRST集合
        self.compute_first_sets()
        
        # 3. 计算FOLLOW集合
        self.compute_follow_sets()
        
        # 4. 构造LL(1)分析表
        self.construct_ll1_table()
        
        # 5. 进行预测分析
        result = self.predictive_parse(tokens)
        
        # 6. 进行智能纠错分析
        if not result:
            self._perform_error_correction()
        
        return result
    
    def _record_syntax_error(self, error_token: Optional[Token], message: str, expected: str, got: str):
        """记录语法错误"""
        line = error_token.line if error_token else 1
        column = error_token.column if error_token else 1
        token_value = error_token.value if error_token else ""
        
        # 生成智能修复建议
        suggestions = self._generate_token_suggestions(expected, got)
        
        error = ErrorInfo(
            error_type=ErrorType.UNEXPECTED_TOKEN if got != "EOF" else ErrorType.MISSING_TOKEN,
            severity=ErrorSeverity.ERROR,
            message=message,
            line=line,
            column=column,
            token_value=token_value,
            suggestions=suggestions
        )
        
        self.error_corrector.add_error(error)
        self.parse_errors.append(message)
    
    def _record_parse_table_error(self, error_token: Optional[Token], non_terminal: str, 
                                 current_input: str, expected_symbols: List[str]):
        """记录解析表查找失败错误"""
        line = error_token.line if error_token else 1
        column = error_token.column if error_token else 1
        token_value = error_token.value if error_token else ""
        
        message = f"非终结符 '{non_terminal}' 无法处理输入符号 '{current_input}'"
        
        # 生成智能修复建议
        suggestions = []
        if expected_symbols:
            suggestions.extend([f"期望符号: {sym}" for sym in expected_symbols[:3]])
        
        # 根据非终结符类型给出具体建议
        suggestions.extend(self._generate_nonterminal_suggestions(non_terminal, current_input))
        
        error = ErrorInfo(
            error_type=ErrorType.SYNTAX,
            severity=ErrorSeverity.ERROR,
            message=message,
            line=line,
            column=column,
            token_value=token_value,
            suggestions=suggestions
        )
        
        self.error_corrector.add_error(error)
        self.parse_errors.append(message)
    
    def _generate_token_suggestions(self, expected: str, got: str) -> List[str]:
        """为令牌错误生成修复建议"""
        suggestions = []
        
        if expected == ";" and got != "EOF":
            suggestions.append("在语句末尾添加分号 ';'")
        elif expected == "FROM" and got in ["WHERE", "ORDER", "GROUP"]:
            suggestions.append("SELECT语句必须包含FROM子句")
        elif expected == "(" and got in ["ID_TOKEN", "STRING", "NUM"]:
            suggestions.append("函数调用或表达式需要括号")
        elif expected == ")" and got in [",", ";", "FROM"]:
            suggestions.append("缺少闭合括号 ')'")
        elif expected == "," and got in ["FROM", "WHERE", "ORDER"]:
            suggestions.append("列表项之间需要逗号分隔")
        elif expected in ["ID_TOKEN"] and got in ["SELECT", "FROM", "WHERE"]:
            suggestions.append("期望标识符（表名或列名）")
        elif expected in ["STRING", "NUM"] and got in ["ID_TOKEN"]:
            suggestions.append("期望常量值")
        else:
            suggestions.append(f"将 '{got}' 替换为 '{expected}'")
        
        return suggestions
    
    def _generate_nonterminal_suggestions(self, non_terminal: str, current_input: str) -> List[str]:
        """为非终结符错误生成修复建议"""
        suggestions = []
        
        if non_terminal == "SelList" and current_input == "FROM":
            suggestions.extend([
                "SELECT后面缺少列名",
                "使用 * 选择所有列",
                "指定具体的列名"
            ])
        elif non_terminal == "FromClause" and current_input in ["WHERE", "ORDER", "GROUP"]:
            suggestions.extend([
                "SELECT语句必须包含FROM子句",
                "指定数据来源表名"
            ])
        elif non_terminal == "WhereClause" and current_input == "ORDER":
            suggestions.extend([
                "WHERE子句需要条件表达式",
                "检查条件语法是否正确"
            ])
        elif non_terminal == "Condition" and current_input in [";", "ORDER", "GROUP"]:
            suggestions.extend([
                "WHERE条件不完整",
                "添加比较表达式"
            ])
        elif "List" in non_terminal and current_input in [";", ")"]:
            suggestions.extend([
                f"{non_terminal}不完整",
                "检查列表语法"
            ])
        
        return suggestions
    
    def _perform_error_correction(self):
        """执行智能纠错分析"""
        # 分析语法错误模式
        if self.parse_errors:
            syntax_errors = self.error_corrector.analyze_syntax_errors("", self.parse_errors)
            for error in syntax_errors:
                self.error_corrector.add_error(error)
        
        # 生成修复建议
        suggestions = self.error_corrector.generate_correction_suggestions("", self.error_corrector.errors)
        for suggestion in suggestions:
            self.error_corrector.add_suggestion(suggestion)
    
    def get_error_report(self) -> str:
        """获取语法分析错误报告"""
        return self.error_corrector.format_error_report()
    
    def get_correction_suggestions(self) -> str:
        """获取修复建议"""
        return self.error_corrector.format_correction_suggestions()
    
    def get_error_summary(self) -> Dict[str, int]:
        """获取错误统计摘要"""
        return self.error_corrector.get_error_summary()
    
    def has_errors(self) -> bool:
        """检查是否有错误"""
        return len(self.error_corrector.errors) > 0
    
    def _get_expected_symbols(self, non_terminal: str) -> List[str]:
        """获取给定非终结符的预期符号列表"""
        if non_terminal in self.ll1_table:
            return list(self.ll1_table[non_terminal].keys())
        return []
    
    def _get_context(self, tokens: List[Token], error_index: int) -> str:
        """获取错误位置的上下文信息"""
        context_range = 3  # 前后各显示3个token
        start = max(0, error_index - context_range)
        end = min(len(tokens), error_index + context_range + 1)
        
        context_tokens = []
        for i in range(start, end):
            if i < len(tokens):
                token = tokens[i]
                if i == error_index:
                    # 标记错误位置
                    context_tokens.append(f">>>{token.value}<<<")
                else:
                    context_tokens.append(token.value)
        
        return " ".join(context_tokens)


def main():
    """测试主函数"""
    # 创建词法分析器和语法分析器
    lexical_analyzer = LexicalAnalyzer()
    syntax_analyzer = SyntaxAnalyzer()
    
    # 测试SQL语句集合
    test_cases = [
        "SELECT name FROM Students;",        # 正确语句
        "SELECT name, age FROM Students;",   # 正确语句
        "SELECT FROM Students;",             # 错误：缺少选择列表
        "SELECT name Students;",             # 错误：缺少FROM关键字
        "SELECT name FROM;",                 # 错误：缺少表名
        "SELECT name, FROM Students;",       # 错误：逗号后缺少列名
    ]
    
    for i, test_sql in enumerate(test_cases, 1):
        print(f"\n{'='*50}")
        print(f"测试用例 {i}:")
        print(f"输入的SQL语句: {test_sql}")
        print()
        
        # 词法分析
        tokens = lexical_analyzer.analyze(test_sql)
        print("词法分析结果:")
        for token in tokens:
            print(f"  {token}")
        print()
        
        # 语法分析
        result = syntax_analyzer.analyze(tokens)
        
        if result:
            print(f"\n✓ 测试用例 {i} 语法分析成功！")
        else:
            print(f"\n✗ 测试用例 {i} 语法分析失败！")
        
        print(f"{'='*50}")


if __name__ == "__main__":
    main()
